package com.banmao.algorithm.No101To200.No101;

import java.util.ArrayList;
import java.util.LinkedList;

public class Solution1 {

    public boolean isSymmetric(TreeNode root) {

        ArrayList<Integer> list = null;
        LinkedList<TreeNode> queue = new LinkedList<>();
        if(root == null) {
            return true;
        }

        // 层序遍历
        queue.add(root);

        while (!queue.isEmpty()) {
            int size = queue.size();

            list = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                if(poll == null) {
                    list.add(null);
                } else {
                    list.add(poll.val);

                    if(poll.left != null) {
                        queue.add(poll.left);
                    } else {
                        queue.add(null);
                    }

                    if(poll.right != null) {
                        queue.add(poll.right);
                    } else {
                        queue.add(null);
                    }
                }
            }
            // 检查层序中是否为镜像
            Boolean flag = check(list);
            if(!flag) {
                return false;
            }
        }
        return true;
    }

    private Boolean check(ArrayList<Integer> list) {
        int j = list.size() - 1;
        for (Integer left : list) {
            Integer right = list.get(j);
            if (left != right) {
                return false;
            }
            j--;
        }
        return true;
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
